/*
 * @lc app=leetcode.cn id=509 lang=rust
 *
 * [509] 斐波那契数
 */

// @lc code=start
impl Solution {
    pub fn fib(n: i32) -> i32 {
        let mut vec = vec![0];
        vec.push(1);
        vec.push(1);

        let mut i = 3;
        while i <= (n+1) as usize {
            vec.push(vec[i-1] + vec[i-2]);
            i += 1;
        }
        return vec[n as usize];
    }
}
// @lc code=end

